package class10;

import com.sun.javafx.sg.prism.web.NGWebView;

import java.util.HashSet;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class Light3 {

    public static int minLight1(String load){
        if (load == null || load.length()==0)
            return 0;
        return process(load.toCharArray(),0,new HashSet<>());
    }

    public static int process(char[] arr, int index,HashSet<Integer> light){
        if (index == arr.length){
            for (int i=0;i<arr.length;i++){
                if (arr[i] != 'X') {
                    if (!light.contains(i-1)  &&
                    !light.contains(i)  &&
                    !light.contains(i+1)
                    ){
                        return Integer.MAX_VALUE;
                    }
                }
            }
            return light.size();
        }else {
            int no = process(arr,index+1,light);
            int yes = Integer.MAX_VALUE;
            if (arr[index] == '.'){
                light.add(index);
                yes = process(arr,index+1,light);
                light.remove(index);
            }
            return Math.min(no,yes);
        }
    }

    public static int minLight2(String load){
        char[] str = load.toCharArray();
        int i=0;
        int light = 0;
        while (i<str.length){
            if (str[i] == 'X'){
                i++;
            }else {
                light++;
                if (i+1 ==str.length){
                    break;
                }else {
                    if (str[i+1] == 'X'){
                        i = i+2;
                    }else {
                        i = i+3;
                    }
                }
            }
        }
        return light;
    }

    public static String randomString(int len){
        char[] res = new char[(int)(Math.random()*len)+1];
        for (int i=0;i<res.length;i++){
            res[i] = Math.random()>0.5?'X':'.';
        }
        return String.valueOf(res);
    }

    public static void main(String[] args) {
        int len = 10;
        int testTime = 1000;
        for (int i=0;i<testTime;i++){
            String str= randomString(len);
            int ans1 = minLight1(str);
            int ans2 = minLight2(str);
            if (ans1 != ans2)
                System.out.println("Oops!");
        }
        System.out.println("finish!");
    }
}
